package 二叉树;

public class No1008前序遍历构造二叉搜索树 {

    /**
     * 返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
     * (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，
     * 对于 node.left 的任何后代，值总 < node.val，
     * 而 node.right 的任何后代，值总 > node.val。
     * 此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）
     * 题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。
     *
     * 示例：
     * 输入：[8,5,1,7,10,12]
     * 输出：[8,5,10,1,7,null,12]
     *
     * 提示：
     * 1 <= preorder.length <= 100
     * 1 <= preorder[i] <= 10^8
     * preorder 中的值互不相同
     */

    public TreeNode bstFromPreorder(int[] preorder) {
        return method2(preorder);
    }

    private int index=0;
    //直接一边的构造,推荐写法
    private TreeNode method2(int[] preorder){
        return createTreeNode(preorder,Integer.MAX_VALUE);
    }

    private TreeNode createTreeNode(int[] preorder,int maxNum){
        if(index==preorder.length||preorder[index]>maxNum){
            //大了就让给右子树去吃
            return null;
        }
        //只有通过了检验 index才++
        TreeNode treeNode=new TreeNode(preorder[index++]);
        treeNode.left=createTreeNode(preorder,treeNode.val);
        treeNode.right=createTreeNode(preorder,maxNum);
        return treeNode;
    }

    //从0开始的构造,不推荐的写法
    private TreeNode method1(int[] preorder){
        TreeNode root=new TreeNode(preorder[0]);

        for (int i = 1; i < preorder.length; i++) {
            addTreeNode(root,preorder[i]);
        }

        return root;
    }

    private TreeNode addTreeNode(TreeNode node, int val){

        if(node==null){
            return new TreeNode(val);
        }

        if(node.val>=val){
            //去左边
            node.left=addTreeNode(node.left,val);
        }else{
            //去右边
            node.right=addTreeNode(node.right,val);
        }

        return node;
    }

    public static void main(String[] args) {
        No1008前序遍历构造二叉搜索树 n=new No1008前序遍历构造二叉搜索树();
        int[] arr={8,5,1,7,10,12};
        TreeNode treeNode = n.bstFromPreorder(arr);
        treeNode.printNode();
    }

}
